-- 2022-8-18

---[[ 马尔可夫链算法

    -- 下一个完整的程序是一个马尔可夫链(Markov chain)算法的实现 该算法由Kernighan和Pike在他们的书The Practice of Programming中进行了描述
    -- 马尔可夫链算法根据哪个单词能出现在基础文本中由n个前序单词组成的序列之后 例来生成伪随机(pseudo-random)文本 对于本例中的实现 我们假定为2

    -- 程序的第一部分读取原始文本并创建一个表 该表的键位每两个单词组成的前缀 值为紧跟这个前缀的单词所组成的列表
    -- 当这个表建好后 程序就利用它来生成随机文本 随机文本中每个单词出现在它之前两个单词后的概率预期出现在基础文本中相同两个谦虚单词后的概率相同
    -- 最终 我们会得到一串相对比较随机的文本 例如 以本书的英文原版作为基础文本 那么该程序的输出形如"Constructors can also traverse a table constructor,
    -- then the parentheses in the following line does the whole file in a field n to store the contents of eash function,but to show its only argument.
    -- If you want to find the maximum element in an array can return both the maximum value and continues showing the prompt and running the code.The 
    -- following words are reserved and cannot be used to convert between degrees and radians

    -- 要将由两个单词组成的前缀作为表的键 需要使用空格来连接两个单词
    function prefix (w1,w2)
        return w1 .. " " .. w2
    end
    -- 我们使用字符串NOWORD(换行符)初始化前缀单词及标记文本的结局 例如 对于文本"the more we try the more we do"而言 构造出的表如下:
    --[=[
        {
            ["\n \n"] = {"the"},
            ["\n the"] = {"more"},
            ["the more"] = {"we","we"},
            ["more we"] = {"try","do"},
            ["we try"] = ["the"],
            ["try the"] = ["more"],
            ["we do"] = {"\n"}
        }
    ]=]
    -- 程序将表保存在变量statetab中 如果要向表中的某个前缀所对应的列表中插入一个新单词 可以使用如下的函数:
    function insert (prefix,value)
        local list = statetab[prefix]
        if list == nil then
            statetab[prefix] = {value}
        else
            list[#list+1] = value
        end
    end
    -- 该函数首先检查某前缀是否已经有了对应的列表 如果没有 则以新值来创建一个新列表 否则 就将新值添加到现有列表的末尾

    -- 为了构造表statetab 我们使用两个变量w1和w2来记录最后读取的两个单词
    -- 我们使用18.1节中的allwords迭代器读取单词 只不过修改了其中"单词"的定义以便将可选的诸如逗号和句号等标点符号包括在内(参见示例19.1)
    -- 对于新读取的每一个单词 把它添加到与w1-w2相关联的列表中 然后更新w1和w2

    -- 在构造完表后 程序便开始生成具有MACGEN个单词的文本 首先 程序重新初始化变量w1和w2
    -- 然后 对于每个前缀 程序对其对应的单词列表中随机地选出一个单词 输出这个单词 并更新w1和w2 示例19.1和19.2给出1了完整的程序
    
    -- 19.1 马尔可夫链程序的辅助定义
    function allwords ()
        local line = io.read() -- 当前行
        local pos = 1 -- 当前行的当前位置
        return function () -- 迭代函数
            while line do -- 当还有行时循环
                local w,e = string.match(line,"%w+[,;,:]?)()",pos)
                if w then -- 发现一个单词?
                    pos = e -- 更新位置
                    return w -- 返回该单词
                else
                    line = io.read() -- 没找到单词;尝试下一行
                    pos = 1 -- 从第一个位置重新开始
                end
            end
            return nil -- 没有行了:迭代结束
        end
    end

    function prefix (w1,w2)
        return w1 .. " " .. w2
    end

    function insert (prefix,value)
        local list = statetab[prefix]
        if list == nil then
            statetab[prefix] = {value}
        else
            list[#list+1] = value
        end
    end

    -- 19.2 马尔科夫链程序
    local MAXGEN = 200
    local NOWORD = "\n"

    -- 创建表
    local w1,w2 = NOWORD,NOWORD
    for nextword in allwords() do
        insert(prefix(w1,w2),nextword)
        w1 = w2
        w2 = nextword
    end
    insert(prefix(w1,w2),NOWORD)

    -- 生成本文
    w1 = NOWORD
    w2 = NOWORD -- 重新初始化
    for i = 1, MAXGEN do
        local list = statetab[prefix(w1,w2)]
        -- 从列表中随机选出一个元素
        local r = math.random(#list)
        local nextword = list[r]
        if nextword == NOWORD then return end
        io.write(nextword," ")
        w1 = w2
        w2 = nextword
    end
--]]